/**
 * https://leetcode.cn/submissions/detail/585456519/
 * 687. 最长同值路径
 * Medium, 黄伟杰 2024.12.06
 * DFS
 */

class Solution
{
    int ans;
    int dfs(TreeNode *rt)
    {
        if (rt == nullptr)
            return -1;
        int L = dfs(rt->left) + 1;
        int R = dfs(rt->right) + 1;
        if (rt->left && rt->left->val != rt->val)
            L = 0;
        if (rt->right && rt->right->val != rt->val)
            R = 0;
        ans = max(ans, L + R); // 寻找最长
        return max(R, L);      // 返回根的深度
    }

public:
    int longestUnivaluePath(TreeNode *root)
    {
        ans = 0;
        dfs(root);
        return ans;
    }
};